/**
 * @projectName leetode
 * @package cn.leetcode
 * @className cn.leetcode.t106
 * @copyright Copyright 2020 Thunisoft, Inc All rights reserved.
 */
package cn.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * t106
 * @description
 * @author fei
 * @date 2025/9/11 14:40
 * @version 1.0
 */
/*
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。



示例 1:


输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]
 */
public class t106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(inorder[i], i);
        }
        return dfs(0,n,inorder,0,n,postorder,map);
    }

    public TreeNode dfs(int inL, int inR, int[] inorder, int postL, int postR, int[] postorder, Map<Integer, Integer> index){
        if (postL == postR){//空节点
            return null;
        }
        int leftSize = index.get(postorder[postR - 1])-inL;
        TreeNode left = dfs(inL,inL+leftSize,inorder,postL,postL+leftSize,postorder,index);
        TreeNode right = dfs(inL+leftSize+1,inR,inorder,postL+leftSize,postR-1,postorder,index);
        return new TreeNode(postorder[postR-1],left,right);
    }

}
